package simpledb.lock;

import simpledb.storage.BufferPool;
import simpledb.transaction.TransactionId;

import java.util.*;
import java.util.concurrent.locks.ReentrantLock;

public class DeadlockDetector {
    // 死锁检测开关
    private final boolean enableDeadlockDetection;
    // 死锁检测间隔（毫秒）
    private final long deadlockCheckInterval;
    // 等待图锁（保证对等待图操作的线程安全）
    private final ReentrantLock waitGraphLock = new ReentrantLock();
    // 等待图: key为等待者，value为被等待的事务集合
    private final Map<TransactionId, Set<TransactionId>> waitGraph = new HashMap<>();
    // 死锁检测线程
    private Thread detectorThread;
    // 线程运行状态
    private volatile boolean isRunning = true;
    // 持有LockManager引用，用于解决死锁时释放锁
    private final LockManager lockManager;
    // 持有BufferPool的引用,用于检测到事务时,事务回滚
    private final BufferPool bufferPool;

    public DeadlockDetector(boolean enableDeadlockDetection, long deadlockCheckInterval, LockManager lockManager, BufferPool bufferPool) {
        this.enableDeadlockDetection = enableDeadlockDetection;
        this.deadlockCheckInterval = deadlockCheckInterval;
        this.lockManager = lockManager;
        this.bufferPool = bufferPool;
        if (enableDeadlockDetection) {
            startDetectorThread();
        }
    }

    // 启动死锁检测线程
    private void startDetectorThread() {
        // lambda方式创建线程，也可以用匿名表达类
        detectorThread = new Thread(() -> {
            System.out.println("[死锁检测] 检测线程启动，间隔: " + deadlockCheckInterval + "ms");
            while (isRunning) {
                try {
                    Thread.sleep(deadlockCheckInterval);
                    detectAndResolveDeadlock();
                    //     sleep，wait被中断时会抛出异常并清空中断标记
                } catch (InterruptedException e) {
                    // 重置中断标记，保证中断这个事情可以继续向上通知
                    Thread.currentThread().interrupt();
                    System.out.println("[死锁检测] 检测线程被中断");
                    break;
                }
            }
            System.out.println("[死锁检测] 检测线程停止");
        }, "Deadlock-Detector");
        // 守护线程会随着主线程的结束而结束
        detectorThread.setDaemon(true);
        detectorThread.start();
    }

    private void detectAndResolveDeadlock() {
        // 先收集需要处理的牺牲者，不立即处理
        List<TransactionId> victims = new ArrayList<>();
        // System.out.println("[死锁检测]");
        try {
            waitGraphLock.lock();
            if (waitGraph.isEmpty()) {
                return;
            }

            // 查找所有死锁环并记录牺牲者
            Set<Set<TransactionId>> cycles = findAllCycles();
            if (!cycles.isEmpty()) {
                System.out.println("[死锁检测] 发现死锁数量: " + cycles.size());
                for (Set<TransactionId> cycle : cycles) {
                    TransactionId victim = cycle.iterator().next();
                    victims.add(victim);
                }
            }
        } finally {
            // 先释放waitGraphLock，再处理死锁，避免持有它时获取pageLock.lock
            if (waitGraphLock.isHeldByCurrentThread()) {
                waitGraphLock.unlock();
            }
        }

        // 处理死锁（释放牺牲者锁），此时已不持有waitGraphLock
        for (TransactionId victim : victims) {
            resolveDeadlock(victim);
        }
    }

    // // 检测并解决死锁
    // private void detectAndResolveDeadlock() {
    //
    //     try {
    //         // 互斥访问有向图
    //         waitGraphLock.lock();
    //         if (waitGraph.isEmpty()) {
    //             return;
    //         }
    //
    //         // 查找所有环（死锁）
    //         Set<Set<TransactionId>> cycles = findAllCycles();
    //         if (!cycles.isEmpty()) {
    //             System.out.println("[死锁检测] 发现死锁数量: " + cycles.size());
    //
    //             // 处理每个死锁环
    //             for (Set<TransactionId> cycle : cycles) {
    //                 // 选择第一个事务作为牺牲者
    //                 TransactionId victim = cycle.iterator().next();
    //                 resolveDeadlock(victim);
    //             }
    //         }
    //     } finally {
    //         if (waitGraphLock.isHeldByCurrentThread()) {
    //             waitGraphLock.unlock();
    //         }
    //     }
    // }
    // Dfs查找等待图中所有环,注意不可以用拓扑排序判断是否有环，因为会破坏图的结构
    private Set<Set<TransactionId>> findAllCycles() {
        // 存储环,HashSet就行，因为是互斥访问的
        Set<Set<TransactionId>> cycles = new HashSet<>();
        // 访问标记
        Set<TransactionId> visited = new HashSet<>();
        // 单词深搜遇到的节点
        Set<TransactionId> recStack = new HashSet<>();
        for (TransactionId tx : waitGraph.keySet()) {
            if (!visited.contains(tx)) {
                findCycles(tx, visited, recStack, new LinkedList<>(), cycles);
            }
        }
        return cycles;
    }
    // 递归查找环的辅助方法
    private void findCycles(TransactionId current, Set<TransactionId> visited, Set<TransactionId> recStack,
                            LinkedList<TransactionId> path, Set<Set<TransactionId>> cycles) {
        // 如果当前节点被遍历过，说明遇到环了
        if (recStack.contains(current)) {
            // path是从起点到当前节点的完整路径
            // index代表当前重复节点第一次出现的位置，截取到path末尾，获取当前死锁的路径
            int index = path.indexOf(current);
            List<TransactionId> cycle = path.subList(index, path.size());
            // 添加到结果集中
            cycles.add(new HashSet<>(cycle));
            return;
        }
        // 如果不在环里边，但是访问过了就访问下一个
        // 例如a->d, c->d
        if (visited.contains(current)) {
            return;
        }
        visited.add(current);
        recStack.add(current);
        path.add(current);
        Set<TransactionId> waitingList = waitGraph.get(current);
        if (waitingList!=null) {
            for (TransactionId next : waitingList) {
                findCycles(next, visited, recStack, path, cycles);
            }
        }
        // 移除当前节点
        recStack.remove(current);
        path.removeLast();
    }
    // 解决死锁：释放牺牲者的所有锁并清理等待图
    private void resolveDeadlock(TransactionId victim) {
        System.out.println("[死锁检测] 选择事务 " + victim + " 作为牺牲者解除死锁");
        // 释放牺牲者的所有锁，由 LockManager 内部调用 removeWaitRelations 清理等待图
        bufferPool.transactionComplete(victim, false);
    }

    /**
     * 批量添加等待关系：tx 等待所有 in txSet 中的事务,避免重复获取锁
     * @param tx 等待者事务
     * @param txSet 被等待的事务集合（通常来自 txLocks.keySet()）
     */
    public void addWaitRelations(TransactionId tx, Set<TransactionId> txSet) {
        if (enableDeadlockDetection && txSet != null && !txSet.isEmpty()) {
            try {
                waitGraphLock.lock();
                // 获取当前事务的等待集合（不存在则创建）
                Set<TransactionId> waitingForSet = waitGraph.computeIfAbsent(tx, k -> new HashSet<>());
                // 批量添加所有被等待的事务（排除自身，避免自环）
                for (TransactionId waitingForTx : txSet) {
                    if (!tx.equals(waitingForTx)) { // 跳过自身，防止等待自己导致的假死锁
                        waitingForSet.add(waitingForTx);
                    }
                }
            } finally {
                if (waitGraphLock.isHeldByCurrentThread()) {
                    waitGraphLock.unlock();
                }
            }
        }
    }

    // 添加等待关系：tx等待waitingForTx,只添加单方面等待
    public void addWaitRelation(TransactionId tx, TransactionId waitingForTx) {
        if (enableDeadlockDetection) {
            try {
                waitGraphLock.lock();
                waitGraph.computeIfAbsent(tx, k->new HashSet<>()).add(waitingForTx);
            }finally {
                if (waitGraphLock.isHeldByCurrentThread()) {
                    waitGraphLock.unlock();
                }
            }
        }
    }

    // 移除事务相关的所有等待关系
    public void removeWaitRelations(TransactionId tx) {
        if (enableDeadlockDetection) {
            try {
                waitGraphLock.lock();
                // 移除tx作为等待者的记录
                waitGraph.remove(tx);

                // 移除其他事务等待tx的记录
                for (Set<TransactionId> waitingFor : waitGraph.values()) {
                    waitingFor.remove(tx);
                }
            } finally {
                if (waitGraphLock.isHeldByCurrentThread()) {
                    waitGraphLock.unlock();
                }
            }
        }
    }
    // 停止死锁检测线程
    public void shutdown() {
        isRunning = false;
        if (detectorThread != null) {
            detectorThread.interrupt();
            try {
                // 等待检测线程释放资源
                detectorThread.join();
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
            }
        }
    }
}
